Search for: All records

We study scheduling mechanisms that explore the trade-off between containing the spread of COVID-19 and performing in-person activity in organizations. Our mechanisms, referred to as group scheduling , are based on partitioning the population randomly into groups and scheduling each group on appropriate days with possible gaps (when no one is working and all are quarantined). Each group interacts with no other group and, importantly, any person who is symptomatic in a group is quarantined. We show that our mechanisms effectively trade-off in-person activity for more effective control of the COVID-19 virus spread. In particular, we show that a mechanism which partitions the population into two groups that alternatively work in-person for five days each, flatlines the number of COVID-19 cases quite effectively, while still maintaining in-person activity at 70% of pre-COVID-19 level. Other mechanisms that partitions into two groups with less continuous work days or more spacing or three groups achieve even more aggressive control of the virus at the cost of a somewhat lower in-person activity (about 50%). We demonstrate the efficacy of our mechanisms by theoretical analysis and extensive experimental simulations on various epidemiological models based on real-world data. 

The K-nearest neighbors is a basic problem in machine learning with numerous applications. In this problem, given a (training) set of n data points with labels and a query point q, we want to assign a label to q based on the labels of the K-nearest points to the query. We study this problem in the k-machine model, a model for distributed large-scale data. In this model, we assume that the n points are distributed (in a balanced fashion) among the k machines and the goal is to compute an answer given a query point to a machine using a small number of communication rounds. Our main result is a randomized algorithm in the k-machine model that runs in O(log K) communication rounds with high success probability (regardless of the number of machines k and the number of points n). The message complexity of the algorithm is small taking only O(k log K) messages. Our bounds are essentially the best possible for comparison-based algorithms. We also implemented our algorithm and show that it performs well in practice. 

Designing effective algorithms for community detection is an important and challenging problem in large-scale graphs, studied extensively in the literature. Various solutions have been proposed, but many of them are centralized with expensive procedures (requiring full knowledge of the input graph) and have a large running time. In this paper, we present a distributed algorithm for community detection in the stochastic block model (also called planted partition model), a widely-studied and canonical random graph model for community detection and clustering. Our algorithm called CDRW(Community Detection by Random Walks) is based on random walks, and is localized and lightweight, and easy to implement. A novel feature of the algorithm is that it uses the concept of local mixing time to identify the community around a given node. We present a rigorous theoretical analysis that shows that the algorithm can accurately identify the communities in the stochastic block model and characterize the model parameters where the algorithm works. We also present experimental results that validate our theoretical analysis. We also analyze the performance of our distributed algorithm under the CONGEST distributed model as well as the k-machine model, a model for large-scale distributed computations, and show that it can be efficiently implemented.